//题目:
// 你有一个背包，最多能容纳的体积是V。

// 现在有n种物品，每种物品仅有1个，第i种物品的体积为vi,​价值为wi。
// （1）求这个背包至多能装多大价值的物品？
// （2）若背包恰好装满，求至多能装多大价值的物品？

// 数据范围： 1≤v,vi,wi≤1000;
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) 
    {
        
        // // write code here  nums[i][0]：体积   nums[i][1]：价值
        // vector<int> ret;
        // //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
        // vector<vector<int>> dp(n+1,vector<int>(v+1));
        // //2.初始化————暂无
        // //3.填表————动态转移方程
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=v;j++)
        //     {
        //         dp[i][j]=dp[i-1][j];//不装第i个物品
        //         if(j-nums[i-1][0]>=0)
        //             dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
        //     }
        // }
        // //4.确定第一个返回值
        // ret.push_back(dp[n][v]);

        // //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
        // memset(&dp,0,sizeof(dp));
        // //2.初始化
        // for(int j=1;j<=v;j++)
        //     dp[0][j]=-1;//表示这种状态不存在
        // //3.填表————动态转移方程
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=v;j++)
        //     {
        //         dp[i][j]=dp[i-1][j];//不装第i个物品
        //         if(j-nums[i-1][0]>=0 && dp[i-1][j-nums[i-1][0]]!=-1)
        //             dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
        //     }
        // }
        // //4.确定第一个返回值
        // if(dp[n][v]==-1)dp[n][v]=0;
        // ret.push_back(dp[n][v]);
        // return ret;

        //空间优化O(N^2)————>O(N)
        vector<int> ret;
        //1.创建dp表————dp[i][j]表示：背包装载第i个物品、体积不超过j时的最大价值
        vector<int> dp(v+1);
        //2.初始化————暂无
        //3.填表————动态转移方程
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=nums[i-1][0];j--)
                dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
        }
        //4.确定第一个返回值
        ret.push_back(dp[v]);

        //创建第二个dp表————dp[i][j]表示：背包装载第i个物品、体积等于j时的最大价值
        memset(&dp,0,sizeof(dp));
        //2.初始化
        for(int j=1;j<=v;j++)
            dp[j]=-1;//表示这种状态不存在
        //3.填表————动态转移方程
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=nums[i-1][0];j--)
            {
                if(dp[j-nums[i-1][0]]!=-1)
                    dp[j]=max(dp[j],dp[j-nums[i-1][0]]+nums[i-1][1]);//装第i个物品
            }
        }
        //4.确定第一个返回值
        if(dp[v]==-1)dp[v]=0;
        ret.push_back(dp[v]);

        return ret;
    }
};